Definition(s)

The stable marriage problem is the problem of finding a stable matching between two equally sized sets of elements given an ordering of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set.

A matching is not stable if:

There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
B also prefers A over the element to which B is already matched.

In other words, a matching is stable when there does not exist any match (A, B) by which both A and B would be individually better off than they are with the element to which they are currently matched.

Algorithm(s)



In [1]:

    
from collections import deque, defaultdict



In [17]:

    
def gale_shapley(men, women):
    free_men = deque(men)
    marriages = defaultdict(lambda: None)
    
    preferences = dict()
    for jane in women:
        for i, john in enumerate(women[jane]):
            preferences[(jane, john)] = i
    
    while free_men:
        john = free_men.popleft()
        
        for jane in men[john]:
            fiance = marriages[jane]
            
            if fiance is None or preferences[(jane, john)] < preferences[(jane, fiance)]:
                marriages[jane] = john
                
                if fiance is not None:
                    free_men.append(fiance)
                break
                    
    return list(sorted((m, w) for w, m in marriages.items()))

Run(s)



In [18]:

    
men = {
    'adam': ['claire', 'diana'],
    'bob': ['diana', 'claire']
}

women = {
    'claire': ['bob', 'adam'],
    'diana': ['adam', 'bob']
}

gale_shapley(men, women)









    Out[18]:





[('adam', 'claire'), ('bob', 'diana')]



In [19]:

    
men = {
    1: [2, 4, 1, 3],
    2: [3, 1, 4, 2],
    3: [2, 3, 1, 4],
    4: [4, 1, 3, 2]
}

women = {
    1: [2, 1, 4, 3],
    2: [4, 3, 1, 2],
    3: [1, 4, 3, 2],
    4: [2, 1, 4, 3]
}

gale_shapley(men, women)









    Out[19]:





[(1, 4), (2, 3), (3, 2), (4, 1)]



In [20]:

    
men = {
    'adam': ['betty', 'claire', 'diana'],
    'bob': ['betty', 'claire', 'diana'],
    'charlie': ['betty', 'claire', 'diana']
}

women = {
    'betty': ['charlie', 'bob', 'adam'],
    'claire': ['charlie', 'bob', 'adam'],
    'diana': ['charlie', 'bob', 'adam']
}

gale_shapley(men, women)









    Out[20]:





[('adam', 'diana'), ('bob', 'claire'), ('charlie', 'betty')]



In [21]:

    
men = {
    'alex': ['alice', 'beatrice', 'christina'],
    'ben': ['beatrice', 'alice', 'christina'],
    'charlie': ['beatrice', 'christina', 'alice']
}

women = {
    'alice': ['alex', 'charlie', 'ben'],
    'beatrice': ['charlie', 'alex', 'ben'],
    'charlie': ['alex', 'charlie', 'ben']
}

gale_shapley(men, women)









    Out[21]:





[('alex', 'alice'), ('ben', 'christina'), ('charlie', 'beatrice')]